package demo1;

import java.util.*;

public class BinaryTree {
    static class TreeNode {
        public Character val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Character val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode treeNode1=new TreeNode('A');
        TreeNode treeNode2=new TreeNode('B');
        TreeNode treeNode3=new TreeNode('C');
        TreeNode treeNode4=new TreeNode('D');
        TreeNode treeNode5=new TreeNode('E');
        treeNode1.left=treeNode2;
        treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;
        treeNode2.right=treeNode5;
        return treeNode1;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root==null){//终止条件
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);

    }
//    public void preOrder1(TreeNode root) {
//        if(root == null) return;
//        Stack<TreeNode> stack = new Stack<>();
//        TreeNode cur = root;
//
//        while (cur != null || !stack.isEmpty()) {
//            while (cur != null) {
//                stack.push(cur);
//                System.out.print(cur.val + " ");
//                cur = cur.left;
//            }
//            TreeNode top = stack.pop();
//            cur = top.right;
//        }
//    }
    public void preOrder1(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        //为什么要加cur！=null
        //1.因为不加cur！=null，stack永远为空，进不了来循环
        //2.因为有时候会出现栈已经为空了，但是cur=top.right不为null的情况
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                System.out.print(cur.val+" ");
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }



    //遍历思路


    List<Character> list=new ArrayList<>();
    public List<Character> preorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    //子问题
    //等于root加左子树的节点+右子树的节点
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
        List<Character> LeftTree=preorderTraversal2(root.left);
        list.addAll(LeftTree);
        List<Character> RightTree=preorderTraversal2(root.right);
        list.addAll(RightTree);
        return list;
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);

    }
    public void inOrder1(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        //为什么要加cur！=null
        //1.因为不加cur！=null，stack永远为空，进不了来循环
        //2.因为有时候会出现栈已经为空了，但是cur=top.right不为null的情况
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }
    // 后序遍历
    public void postOrder(TreeNode root) {
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");

    }
//    public void postOrder1(TreeNode root){
//        if(root==null){
//            return;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        TreeNode prev=null;
//        while(cur!=null||!stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                cur=cur.left;
//            }
//            TreeNode peek=stack.peek();
//            if(peek.right==null||peek.right==prev){
//                System.out.print(peek.val+" ");
//                stack.pop();
//                prev=peek;
//            }else{
//                cur=peek.right;
//
//            }
//        }
//    }
//    public void postOrder1(TreeNode root){
//        if(root==null){
//            return;
//        }
//        Stack<TreeNode> stack=new Stack<>();
//        TreeNode cur=root;
//        //引入一个prev防止重复打印
//        TreeNode prev=null;
//        while(cur!=null||!stack.isEmpty()){
//            while(cur!=null){
//                stack.push(cur);
//                cur=cur.left;
//            }
//            TreeNode peek=stack.peek();
//            if(peek.right==null||peek.right==prev){
//                System.out.print(peek.val+" ");
//                stack.pop();
//                //关键点
//                prev=peek;
//            }else{
//                cur=peek.right;
//            }
//        }
//    }
    public void postOrder1(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode peek=stack.peek();
            if(peek.right==null||peek.right==prev){
                System.out.print(peek.val+" ");
                prev=peek;
                stack.pop();
            }else{
                cur=peek.right;
            }
        }

    }



    public static int Nodesize=0;
    // 获取树中节点的个数
    public void size(TreeNode root) {
        if(root==null){
            return;
        }
        Nodesize++;
        size(root.left);
        size(root.right);
    }



//子问题，左子树节点加右子树节点+1
    public int size2(TreeNode root) {
        if(root==null){
            return 0;
        }
        return size2(root.left)+size2(root.right)+1;
    }

    /**
     * 获取叶子节点的个数
     *  什么是叶子
     * @param root
     * @return
     */

    public static int LeafNodeSize=0;
    public void getLeafNodeCount(TreeNode root) {
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            LeafNodeSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);


    }

    //子问题：叶子节点总数=左子树中叶子节点的总数+右子数中叶子节点的总数
    public int getLeafNodeCount2(TreeNode root) {
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);

    }
    //获取树的第k层有几个节点
    //子问题:树的第k层的节点=左子树的k-1层节点+右子数的k-1层节点+1
    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1)+1;
    }

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(logN)
     * @param root
     * @return
     */
    //子问题：树的高度=左子树和右子树当中高度的最大值+1
    public int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;

    }

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(logN)
     * @param root
     * @param val
     * @return
     */
    //找关键字：子问题
    //1.先找root 如果没有
    //2.再找左子树  如果没有
    //3.再找右子树  如果没有
    //则就是没找到
    public TreeNode findVal(TreeNode root, char val) {
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        TreeNode LeftTree=findVal(root.left,val);
        if(LeftTree!=null){
            return LeftTree;
        }
        TreeNode RightTree=findVal(root.right,val);
        if(RightTree!=null){
            return RightTree;
        }
        return null;


    }
    public void cengxubianli(TreeNode root){
        if(root==null){
            return;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode p=queue.poll();
            System.out.print(p.val+" ");
            if(p.left!=null){
                queue.offer(p.left);
            }
            if(p.right!=null){
                queue.offer(p.right);
            }

        }

    }
    public boolean is_wanquantree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            break;//如果cur=null，就直接用break跳出循环
        }
        while(!queue.isEmpty()){
            TreeNode peek=queue.peek();
            if(peek!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }
//    class Solution {
//        public boolean isSymmetric(TreeNode root) {
//            if(root==null){
//                return true;
//            }
//            return isSymmetricChild(root.left,root.right);
//        }
//
//
//        public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
//            if(leftTree!=null&&rightTree==null||leftTree==null&&rightTree!=null){
//                return false;
//            }
//            if(leftTree==null&&rightTree==null){
//                return true;
//            }
//            if(leftTree.val!=rightTree.val){
//                return false;
//            }
//            return isSymmetricChild(leftTree.left,rightTree.right)&&isSymmetricChild(leftTree.right,rightTree.left);
//
//
//        }
//    }
//    public class Solution1 {
//        TreeNode prev=null;
//        public void ConvertChild(TreeNode root){
//            //进行中序排列
//            if(root==null){
//                return;
//            }
//            ConvertChild(root.left);
//            //打印
//            root.left=prev;
//            if(prev!=null){
//                prev.right=root;
//            }
//            prev=root;
//            ConvertChild(root.right);
//
//        }
//        public TreeNode Convert(TreeNode pRootOfTree) {
//            if(pRootOfTree==null){
//                return null;
//            }
//            ConvertChild(pRootOfTree);
//            //找头节点
//            TreeNode head=pRootOfTree;
//            while(head.left!=null){
//                head=head.left;
//            }
//            return head;
//
//        }
//    }
//    class Solution2 {
//        public boolean isSameTree(TreeNode p, TreeNode q) {
//            if(p==null&&q!=null||p!=null&&q==null){
//                return false;
//            }
//            if(p==null&&q==null){
//                return true;
//            }
//            if(p.val!=q.val){
//                return false;
//            }
//            return isSameTree(p.left,q.left)&isSameTree(p.right,q.right);
//        }
//    }
//    class Solution10 {
//        public TreeNode invertTree(TreeNode root) {
//            if(root==null){
//                return null;
//            }
//            if(root.left==null&&root.right==null){
//                return root;
//            }
//            TreeNode tmp=root.left;
//            root.left=root.right;
//            root.right=tmp;
//            invertTree(root.left);
//            invertTree(root.right);
//            return root;
//        }
//    }
//    class Solution9{
//        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//            if(root==null){
//                return false;
//            }
//            if(isSameTree(root,subRoot)){
//                return true;
//            }
//            if(isSubtree(root.left,subRoot)){
//                return true;
//            }
//            if(isSubtree(root.right,subRoot)){
//                return true;
//            }
//            return false;
//
//        }
//        public boolean isSameTree(TreeNode p, TreeNode q) {
//            if(p==null&&q!=null||p!=null&&q==null){
//                return false;
//            }
//            if(p==null&&q==null){
//                return true;
//            }
//            if(p.val!=q.val){
//                return false;
//            }
//            return isSameTree(p.left,q.left)&isSameTree(p.right,q.right);
//        }
//    }
//    class Solution4 {
//        public boolean isSymmetric(TreeNode root) {
//            if(root==null){
//                return true;
//            }
//            return isSameTree(root.left,root.right);
//        }
//        public boolean isSameTree(TreeNode p, TreeNode q) {
//            if(p==null&&q!=null||p!=null&&q==null){
//                return false;
//            }
//            if(p==null&&q==null){
//                return true;
//            }
//            if(p.val!=q.val){
//                return false;
//            }
//            return isSameTree(p.left,q.right)&isSameTree(p.right,q.left);
//        }
//
//    }
//    class Solution11 {
//        public boolean isBalanced(TreeNode root) {
//            if(root==null){
//                return true;
//            }
//            TreeNode leftTree=root.left;
//            TreeNode rightTree=root.right;
//            int c=Math.abs(isBalancedChild(leftTree)-isBalancedChild(rightTree));
//            if(c>1){
//                return false;
//            }
//            return isBalanced(root.left)&&isBalanced(root.right);
//        }
//        public int isBalancedChild(TreeNode root){
//            if(root==null){
//                return 0;
//            }
//            //子问题思路：树的高度=左子树的高度与右子树的高度当中的最大值+1;
//            return Math.max(isBalancedChild(root.left),isBalancedChild(root.right))+1;
//        }
//    }
//    public class Solution15 {
//        TreeNode prev=null;
//        public void ConvertChild(TreeNode root){
//            if(root==null){
//                return;
//            }
//            ConvertChild(root.left);
//            //打印
//            root.left=prev;
//            if(prev!=null){
//                prev.right=root;
//            }
//            prev=root;
//            ConvertChild(root.right);
//        }
//        public TreeNode Convert(TreeNode pRootOfTree) {
//            if(pRootOfTree==null){
//                return pRootOfTree;
//            }
//            //得先用中序遍历排
//            ConvertChild(pRootOfTree);
//            TreeNode head=pRootOfTree;
//            while(head.left!=null){
//                head=head.left;
//            }
//            return head;
//
//
//        }
//    }
//    class Solution16 {
//        public boolean isBalanced(TreeNode root) {
//            if(root==null){
//                return true;
//            }
//            return isBalancedChild(root)>0;
//
//        }
//        public int isBalancedChild(TreeNode root){
//            if(root==null){
//                return 0;
//            }
//            int leftTree=isBalancedChild(root.left);
//            if(leftTree<0){//回归过程，这个基本上都用得到，左先执行，要检查，
//                return -1;
//            }
//            int rightTree=isBalancedChild(root.right);
//            if(rightTree>=0&&Math.abs(leftTree-rightTree)<=1){
//                return Math.max(isBalancedChild(root.left),isBalancedChild(root.right))+1;
//            }else{
//                return -1;
//            }
//        }
//    }
//    class TreeNode{
//        public TreeNode right;
//        public TreeNode left;
//        public char val;
//        public TreeNode(char val){
//            this.val=val;
//        }
//    }
//
//    // 注意类名必须为 Main, 不要有任何 package xxx 信息
//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            // 注意 hasNext 和 hasNextLine 的区别
//            while (in.hasNextLine()) { // 注意 while 处理多个 case
//                String s=in.nextLine();
//                TreeNode i=createTree(s);
//                zhongxubianli(i);
//            }
//        }
//        public static int i=0;
//        public static TreeNode createTree(String s){
//            TreeNode root=null;
//            if(s.charAt(i)!='#'){
//                //先创建根节点
//                root=new TreeNode(s.charAt(i));
//                i++;
//                //分别创建左右子树
//                root.left=createTree(s);
//                root.right=createTree(s);
//            }else{
//                i++;
//            }
//            return root;
//
//        }
//        public static void zhongxubianli(TreeNode root){
//            if(root==null){
//                return;
//            }
//            zhongxubianli(root.left);
//            System.out.print(root.val+" ");
//            zhongxubianli(root.right);
//        }
//    }

    //判断二叉树是不是完全二叉树
//    public boolean isCompleteTree(TreeNode root){
//        if(root==null){
//            return true;
//        }
//        Queue<Character> queue=new LinkedList<>();
//        TreeNode cur=root;
//        if(queue.isEmpty()){
//            queue.offer(cur);
//        }
//        while(cur!=null){
//            queue.poll();
//            queue.offer(cur.left);
//            queue.offer(cur.right)
//        }
//
//
//
//    }


}
